//package com.gitee.feizns.explore.data_structure.tree.cus.rbt;
//
//import com.gitee.feizns.explore.data_structure.tree.cus.Node;
//
//import java.util.Collection;
//import java.util.Set;
//
///**
// * @author feizns
// * @since 2019/12/18
// */
//public class RbtImpl2<K extends Comparable<K>, V> implements Rbt<RbtImpl2.RBNode, K, V> {
//
//    public static void main(String[] args) {
//        RbtImpl2 t = new RbtImpl2();
//        t.put(1, 2);
//        t.put(2, 2);
//        t.put(3, 2);
//        t.put(4, 2);
//        t.put(5, 2);
//        t.put(6, 2);
//        t.put(7, 2);
//        t.put(8, 2);
//        t.put(9, 2);
//        t.put(10, 2);
//        System.out.println("===============================");
//        t.recursiveMiddleEach((k, v) -> System.out.println(k));
//        t.remove(10);
//        t.remove(9);
//        t.remove(8);
//        t.remove(7);
//        t.remove(6);
//        t.remove(5);
//        t.remove(4);
////        t.remove(3);
////        t.remove(2);
////        t.remove(1);
//        System.out.println("===============================");
//        t.recursiveMiddleEach((k, v) -> System.out.println(k));
//    }
//
//    private RBNode<K, V> root;
//
//    private int size;
//
//    @Override
//    public Node root() {
//        return root;
//    }
//
//    @Override
//    public int size() {
//        return size;
//    }
//
//    @Override
//    public V get(Object key) {
//        RBNode<K, V> rbNode = find(root, (K) key);
//        return rbNode != null ? rbNode.v : null;
//    }
//
//    private RBNode<K, V> find(RBNode<K, V> root, K k) {
//        if ( root != null ) {
//            int comp = k.compareTo(root.k);
//            if ( comp < 0 )
//                return find(root.left, k);
//            else if ( comp > 0 )
//                return find(root.right, k);
//            else
//                return root;
//        }
//        return null;
//    }
//
//    @Override
//    public V put(K key, V value) {
//        NAndV ret = put(root, key, value);
//        root = ret.n;
//        root.color = BLACK;
//        return ret.v;
//    }
//
//    private NAndV put(RBNode<K, V> root, K k, V v) {
//        if ( root == null ) {
//            size++;
//            return new NAndV(new RBNode(k, v), null);
//        }
//
//        V val;
//        int comp = k.compareTo(root.k);
//        if ( comp < 0 ) {
//            NAndV ret = put(root.left, k, v);
//            root.left = ret.n;
//            if ( !isR(root) ) {
//                 if ( !isR(root.right) ) {
//                     if ( isR(root.left) && isR(root.left.right) )
//                         root = leftRotate(root.left);
//                     if ( isR(root.left) && isR(root.left.left) )
//                         root = rightRotate(root);
//                 } else {
//                     if ( isR(root.left) && (isR(root.left.right) || isR(root.left.left)) )
//                         flipColor(root);
//                 }
//            }
//            val = ret.v;
//        } else if ( comp > 0 ) {
//            NAndV ret = put(root.right, k, v);
//            root.right = ret.n;
//            if ( !isR(root) ) {
//                if ( !isR(root.left) ) {
//                    if ( isR(root.right) && isR(root.right.left) )
//                        root = rightRotate(root.right);
//                    if ( isR(root.right) && isR(root.right.right) )
//                        root = leftRotate(root);
//                } else {
//                    if ( isR(root.right) && (isR(root.right.right) || isR(root.right.left)) )
//                        flipColor(root);
//                }
//            }
//            val = ret.v;
//        } else
//            val = root.setValue(v);
//        return new NAndV(root, val);
//    }
//
//    private void flipColor(RBNode<K, V> root) {
//        if ( root != null ) {
//            root.color = RED;
//            root.left.color = BLACK;
//            root.right.color = BLACK;
//        }
//    }
//
//    private boolean isR(RBNode node) {
//        return node != null && node.color == RED;
//    }
//
//    private boolean isB(RBNode node) {
//        return node == null || node.color == BLACK;
//    }
//
////    private RBNode<K, V> leftRotate(RBNode<K, V> node) {
////        RBNode<K, V> right = node.right();
////        node.right = right.left;
////        right.left = node;
////        right.color = node.color;
////        node.color = RED;
////        return right;
////    }
////
////    private RBNode<K, V> rightRotate(RBNode<K, V> node) {
////        RBNode<K, V> left = node.left();
////        node.left = left.right;
////        left.right = node;
////        left.color = node.color;
////        node.color = RED;
////        return left;
////    }
//
//    @Override
//    public V remove(Object key) {
//        ReNAndV nAndV = remove(root, null, (K) key);
//        root = nAndV.p != null ? nAndV.p : nAndV.n;
//        return nAndV.v;
//    }
//
//    private ReNAndV remove(RBNode curt, RBNode parent, K k) {
//        if ( curt != null ) {
//            V v = (V) curt.v;
//            int comp = k.compareTo((K) curt.k);
//            if ( comp < 0 ) {
//                if ( isB(curt) && isB(curt.left) && isB(curt.right) ) {
//                    toRed(curt.left);
//                    toRed(curt.right);
//                }
//
//            }
//        }
//        return null;
//    }
//
//    private void toRed(RBNode node) {
//        if ( node != null )
//            node.color = RED;
//    }
//
////    private ReNAndV remove(RBNode curt, RBNode parent, K k) {
////        if ( curt != null ) {
////            int comp = k.compareTo((K) curt.k);
////            if ( comp < 0 ) {
////                ReNAndV nAndV = remove(curt.left, curt, k);
////                if ( nAndV.p != null ) {
////                    curt = nAndV.p;
////                    if ( parent != null )
////                        parent.left = curt;
////                } else {
////                    curt.left = nAndV.n;
////                    if ( nAndV.reCurt ) {
////                        if ( parent == null )
////                            return new ReNAndV(merge(curt.left, curt.right), nAndV.v);
////                        return removeBlack(curt, parent);
////                    }
////                }
////                return new ReNAndV(curt, nAndV.v);
////            } else if ( comp > 0 ) {
////                ReNAndV nAndV = remove(curt.right, curt, k);
////                if ( nAndV.p != null ) {
////                    curt = nAndV.p;
////                    if ( parent != null )
////                        parent.right = curt;
////                } else {
////                    curt.right = nAndV.n;
////                    if ( nAndV.reCurt ) {
////                        if ( parent == null )
////                            return new ReNAndV(merge(curt.left, curt.right), nAndV.v);
////                        ReNAndV andV = removeBlack(curt, parent);
////                        if ( !andV.reCurt ) {
////
////                            return new ReNAndV();
////                        }
////                        return removeBlack(curt, parent);
////                    }
////                }
////                return new ReNAndV(curt, nAndV.v);
////            } else {
////                V v = (V) curt.v;
////                if ( curt.left != null && curt.right != null && parent == null ) {
////                    size--;
////                    return new ReNAndV(merge(curt.left, curt.right), v);
////                } else if ( curt.right != null ) {
////                    RBNode<K, V> min = min(curt.right);
////                    ReNAndV nAndV = remove(curt.right, curt, min.k);
////                    curt.k = min.k;
////                    curt.v = min.v;
////                    curt.right = nAndV.n;
////                    return new ReNAndV(curt, v);
////                } else if ( curt.left != null ){
////                    RBNode<K, V> max = max(curt.left);
////                    ReNAndV nAndV = remove(curt.left, curt, max.k);
////                    curt.k = max.k;
////                    curt.v = max.v;
////                    curt.left = nAndV.n;
////                    return new ReNAndV(curt, v);
////                } else {
////                    if ( isR(curt) ) {
////                        size--;
////                        return new ReNAndV(null, v);
////                    } else {
////                        return removeBlack(curt, parent);
////                    }
////                }
////            }
////        }
////        return new ReNAndV(null, null);
////    }
////
////    private ReNAndV removeBlack(RBNode curt, RBNode parent) {
////        if ( isLeft(curt, parent) ) {
////            RBNode sibling = parent.right;
////            if ( isB(sibling) && isR(sibling.left) ) {
////                parent.right = rightRotate(sibling);
////                sibling = parent.right;
////            }
////
////            if ( isB(sibling) && isR(sibling.right) ) {
////                parent.left = null;
////                parent = leftRotate(parent);
////                parent.right.color = BLACK;
////                return pAndV(parent, (V) curt.v);
////            }
////
////            if ( isR(parent) ) {
////                parent.left = null;
////                return pAndV(leftRotate(parent), (V) curt.v);
////            }
////
////            if ( isB(parent) && isR(sibling) ) {
////                parent.left = null;
////                if ( sibling.right == null )
////                    sibling = rightRotate(sibling);
////                return new ReNAndV(leftRotate(parent), (V) curt.v);
////            }
////
////            RBNode newNode = new RBNode(parent.k, parent.v, BLACK);
////            newNode.right = new RBNode(sibling.k, sibling.v);
////            ReNAndV ret = new ReNAndV();
////            ret.n = newNode;
////            ret.reCurt = true;
////            return ret;
////        } else {
////            RBNode sibling = parent.left;
////            if ( isB(sibling) && isR(sibling.right) ) {
////                parent.left = leftRotate(sibling);
////                sibling = parent.left;
////            }
////
////            if ( isB(sibling) && isR(sibling.left) ) {
////                parent.right = null;
////                parent = leftRotate(parent);
////                parent.left.color = BLACK;
////                return pAndV(parent, (V) curt.v);
////            }
////
////            if ( isR(parent) ) {
////                RBNode newParent = new RBNode(parent.k, parent.v, BLACK);
////                newParent.left = new RBNode(sibling.k, sibling.v);
////                return pAndV(newParent, (V) curt.v);
////            }
////
////            if ( isB(parent) && isR(sibling) ) {
////                parent.right = null;
////                if ( sibling.left == null )
////                    sibling = leftRotate(sibling);
////                return new ReNAndV(rightRotate(parent), (V) curt.v);
////            }
////
////            RBNode newNode = new RBNode(parent.k, parent.v, BLACK);
////            newNode.left = new RBNode(sibling.k, sibling.v);
////            ReNAndV ret = new ReNAndV();
////            ret.n = newNode;
////            ret.reCurt = true;
////            return ret;
////        }
////    }
//
////    private ReNAndV remove(RBNode curt, RBNode parent, K k) {
////        if ( curt != null ) {
////            int comp = k.compareTo((K) curt.k);
////            if ( comp < 0 ) {
////                ReNAndV nAndV = remove(curt.left, curt, k);
////                if ( nAndV.p != null ) {
////                    curt = nAndV.p;
////                    if ( parent != null )
////                        parent.left = curt;
////                } else
////                    curt.left = nAndV.n;
////                return new ReNAndV(curt, nAndV.v);
////            } else if ( comp > 0 ){
////                ReNAndV nAndV = remove(curt.right, curt, k);
////                if ( nAndV.p != null ) {
////                    curt = nAndV.p;
////                    if ( parent != null )
////                        parent.right = curt;
////                } else
////                    curt.right = nAndV.n;
////                return new ReNAndV(curt, nAndV.v);
////            } else {
////                if ( parent == null ) {
////                    size--;
////                    if ( curt.left == null && curt.right == null )
////                        return new ReNAndV(null, (V) curt.v);
////                    else if ( curt.left == null )
////                        return new ReNAndV(parent.right, (V) curt.v);
////                    else if ( curt.right == null )
////                        return new ReNAndV(parent.left, (V) curt.v);
////                    else
////                        return new ReNAndV(merge(curt.left, curt.right), (V) curt.v);
////                } else if ( curt.left == null && curt.right == null ) {
////                    if ( isR(curt) ) {
////                        size--;
////                        return new ReNAndV(null, (V) curt.v);
////                    } else {
////                        RBNode sibling;
////                        RBNode newNode = null;
////                        if ( isLeft(curt, parent) ) {
////                            sibling = parent.right;
////                            if ( sibling != null ) {
////                                if ( !isR(sibling) && (isR(sibling.left) || isR(sibling.right)) ) {
////                                    if ( !isR(sibling.right) )
////                                        parent.right = rightRotate(sibling);
////                                    parent.left = null;
////                                    return pAndV(leftRotate(parent), (V) curt.v);
////                                }
////                                newNode = new RBNode(parent.k, parent.v, BLACK);
////                                newNode.right = new RBNode(sibling.k, sibling.v);
////                                newNode.right.left = sibling.left;
////                                newNode.right.right = sibling.right;
////                                parent.left = null;
////                            }
////                        } else {
////                            sibling = parent.left;
////                            if ( sibling != null ) {
////                                if ( !isR(sibling) && (isR(sibling.left) || isR(sibling.right)) ) {
////                                    if ( !isR(sibling.left) )
////                                        parent.left = leftRotate(sibling);
////                                    parent.right = null;
////                                    return pAndV(rightRotate(parent), (V) curt.v);
////                                }
////                                newNode = new RBNode(parent.k, parent.v, BLACK);
////                                newNode.left = new RBNode(sibling.k, sibling.v);
////                                newNode.left.left = sibling.left;
////                                newNode.left.right = sibling.right;
////                                parent.right = null;
////                                parent.left = null;
////                            }
////                        }
////                        ReNAndV nAndV = remove(root, null, (K) parent.k);
////                        root = nAndV.p != null ? nAndV.p : nAndV.n;
////                        newNode = newNode != null ? newNode : parent;
////                        return pAndV(newNode, (V) curt.v);
////                    }
////                } else if ( curt.right == null ) {
////                    RBNode<K, V> max = max(curt.left);
////                    V v = (V) curt.v;
////                    ReNAndV nAndV = remove(curt.left, curt, max.k);
////                    if ( nAndV.p != null ) {
////                        curt = nAndV.p;
////                        parent.left = curt;
////                    } else
////                        curt.left = nAndV.n;
////                    curt.k = max.k;
////                    curt.v = max.v;
////                    return new ReNAndV(curt, v);
////                } else {
////                    RBNode<K, V> min = min(curt.right);
////                    V v = (V) curt.v;
////                    ReNAndV nAndV = remove(curt.right, curt, min.k);
////                    if ( nAndV.p != null ) {
////                        curt = nAndV.p;
////                        parent.right = curt;
////                    } else
////                        curt.right = nAndV.n;
////                    curt.k = min.k;
////                    curt.v = min.v;
////                    return new ReNAndV(curt, v);
////                }
////            }
////        }
////        return new ReNAndV(null, null);
////    }
//
////    private RBNode mergeLeft(RBNode p) {
////        RBNode left = p.left;
////        RBNode ret = new RBNode(left.k, left.v);
////        ret.left = left.left;
////        ret.right = left.right;
////
////    }
//
//    private RBNode merge(RBNode l, RBNode r) {
//        if ( l.right != null && r.left != null ) {
//            r.left = l;
//            l.right = merge(l.right, r.left);
//            return r;
//        } else if ( r.left != null ) {
//            l.right = r.left;
//            r.left = l;
//            return r;
//        } else {
//            r.left = l;
//            return r;
//        }
//    }
//
//    private RBNode<K, V> leftRotate(RBNode node) {
//        RBNode right = node.right;
//        node.right = right.left;
//        right.left = node;
//        right.color = node.color;
//        node.color = RED;
//        return right;
//    }
//
//    private RBNode<K, V> rightRotate(RBNode node) {
//        RBNode left = node.left;
//        node.left = left.right;
//        left.right = node;
//        left.color = node.color;
//        node.color = RED;
//        return left;
//    }
//
//    private boolean isLeft(RBNode curt, RBNode parent) {
//        return parent.left == curt;
//    }
//
//    private boolean isRight(RBNode right, RBNode parent) {
//        return parent.right == right;
//    }
//
//    private RBNode<K, V> min(RBNode root) {
//        RBNode<K, V> tmp = root;
//        while ( tmp.left != null )
//            tmp = tmp.left;
//        return tmp;
//    }
//
//    private RBNode<K, V> max(RBNode root) {
//        RBNode<K, V> tmp = root;
//        while ( tmp.right != null )
//            tmp = tmp.right;
//        return tmp;
//    }
//
//    @Override
//    public void clear() {
//        root = null;
//        size = 0;
//    }
//
//    @Override
//    public Set<K> keySet() {
//        return null;
//    }
//
//    @Override
//    public Collection<V> values() {
//        return null;
//    }
//
//    @Override
//    public Set<Entry<K, V>> entrySet() {
//        return null;
//    }
//
//    private ReNAndV pAndV(RBNode p, V v) {
//        ReNAndV re = new ReNAndV();
//        re.p = p;
//        re.v = v;
//        return re;
//    }
//
//    private class ReNAndV {
//
//        private boolean reCurt;
//
//        private RBNode p;
//
//        private RBNode n;
//
//        private V v;
//
//        public ReNAndV(RBNode n, V v) {
//            this.n = n;
//            this.v = v;
//        }
//
//        public ReNAndV() { }
//
//    }
//
//    private class NAndV {
//
//        private RBNode n;
//
//        private V v;
//
//        public NAndV(RBNode n, V v) {
//            this.n = n;
//            this.v = v;
//        }
//    }
//
//    private static boolean BLACK = true;
//
//    private static boolean RED = false;
//
//    static class RBNode<K extends Comparable<K>, V> implements Node<RBNode<K, V>, K, V> {
//
//        K k;
//
//        V v;
//
//        boolean color;
//
//       RBNode<K, V> left, right;
//
//        public RBNode(K k, V v) {
//            this.k = k;
//            this.v = v;
//            this.color = RED;
//        }
//
//        public RBNode(K k, V v, boolean color) {
//            this.k = k;
//            this.v = v;
//            this.color = color;
//        }
//
//        @Override
//        public K key() {
//            return k;
//        }
//
//        @Override
//        public void key(K k) {
//            this.k = k;
//        }
//
//        @Override
//        public V val() {
//            return v;
//        }
//
//        @Override
//        public void val(V v) {
//            this.v = v;
//        }
//
//        @Override
//        public RBNode<K, V> left() {
//            return left;
//        }
//
//        @Override
//        public void left(RBNode<K, V> left) {
//            this.left = left;
//        }
//
//        @Override
//        public RBNode<K, V> right() {
//            return right;
//        }
//
//        @Override
//        public void right(RBNode<K, V> right) {
//            this.right = right;
//        }
//
//        public V setValue(V v) {
//            V old = this.v;
//            this.v = v;
//            return old;
//        }
//
//    }
//
//    public static class EntryImpl<K, V> implements Entry<K, V> {
//
//        K k;
//
//        V v;
//
//        public EntryImpl(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//
//        @Override
//        public K getKey() {
//            return k;
//        }
//
//        @Override
//        public V getValue() {
//            return v;
//        }
//
//        @Override
//        public V setValue(V value) {
//            V old = v;
//            this.v = value;
//            return old;
//        }
//
//    }
//
//}
